差分矩阵

定义

这里也涉及到两个矩阵，原矩阵是差分矩阵的前缀和矩阵。

用途

能 快速多次 对某一个子矩阵进行加减。

实现

• 时间复杂度：
  1. 构造差分数组：$O(n^2)$
  2. 对子矩阵加减：$O(1)$
  3. 求前缀和：$O(n^2)$

题目链接

Acwing链接

main

#include<iostream>
using namespace std;

const int N = 1010;
int a[N][N], d[N][N];

void insert(int x1, int y1, int x2, int y2, int c);

int main() {
    
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    
    // 生成差分矩阵
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            insert(i, j, i, j, mydata[i][j]);
        }
    }
    
    while(q--) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        // 在指定范围插入相应的值
        insert(x1, y1, x2, y2, c);
    }
    
    // 对差分矩阵求前缀和
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            mydata[i][j] = dif[i][j] + mydata[i-1][j] + mydata[i][j-1] - mydata[i-1][j-1];
        }
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cout << mydata[i][j] << " ";         
        }
        cout << endl;
    }
    
    return 0;
}

对某一子矩阵进行加减

void insert(int x1, int y1, int x2, int y2, int c) {
    d[x1][y1] += c;
    d[x2+1][y1] -= c;
    d[x1][y2+1] -= c;
    d[x2+1][y2+1] += c;
}